package de.tum.se.sudoku.logic;

import de.tum.se.sudoku.impl.Cell;
import de.tum.se.sudoku.impl.FixedCell;
import de.tum.se.sudoku.impl.Grid;
import de.tum.se.sudoku.impl.VariableCell;

public class SolverBackTrack implements ISolver {

	private Grid grid;

	/** Checks if num is an acceptable value for the given row */
	protected boolean checkRow(int row, int value) {
		Cell[] gridRow = grid.getRow(row);

		for (Cell cell : gridRow) {
			if (cell.getValue() == value)
				return false;
		}

		return true;
	}

	/** Checks if num is an acceptable value for the given column */
	protected boolean checkCol(int col, int value) {
		Cell[] gridCol = grid.getCol(col);
		for (Cell cell : gridCol) {
			if (cell.getValue() == value)
				return false;
		}

		return true;
	}

	/**
	 * Checks if num is an acceptable value for the unit around row and col *
	 * Units: 0|1|2 3|4|5 6|7|8
	 */
	protected boolean checkBox(int row, int col, int value) {
		Cell[][] units = grid.getUnits();
		int unit; // we want THIS unit

		if (row <= 2 && col <= 2)
			unit = 0;
		else if (row <= 2 && col <= 5)
			unit = 1;
		else if (row <= 2 && col <= 8)
			unit = 2;
		else if (row <= 5 && col <= 2)
			unit = 3;
		else if (row <= 5 && col <= 5)
			unit = 4;
		else if (row <= 5 && col <= 8)
			unit = 5;
		else if (row <= 8 && col <= 2)
			unit = 6;
		else if (row <= 8 && col <= 5)
			unit = 7;
		else
			unit = 8;

		for (Cell cell : units[unit]) {
			if (cell.getValue() == value)
				return false;
		}

		return true;
	}

	/** This method is called by the browser to start the applet */
	/*
	 * public void start() { // This statement will start the method 'run' to in
	 * a new thread (new Thread(this)).start() ; }
	 */

	/** The active part begins here */
	public Grid solve(Grid grid) {
		try {
			this.grid = grid;
			// Start to solve the puzzle in the left upper corner
			backtrack(0, 0);

		} catch (Exception e) {
		}

		return this.grid;
	}

	/** Recursive function to find a valid number for one single cell */
	public void backtrack(int row, int col) throws Exception {

		// Throw an exception to stop the process if the puzzle is solved
		if (row > 8) {
			System.out.println("Last grid is the solution!!!");
			throw new Exception("Solution found");
		}
		// If the cell is not empty, continue with the next cell
		if (grid.getCell(row, col) instanceof FixedCell) {
			next(row, col);
		} else {
			// Find a valid number for the empty cell
			for (int num = 1; num < 10; num++) {
				if (checkRow(row, num) && checkCol(col, num)
						&& checkBox(row, col, num)) {
					grid.setCell(row, col, new VariableCell(num));
					grid.printGrid();

					// Delegate work on the next cell to a recursive call
					next(row, col);
				}
			}

			// No valid number was found, clean up and return to caller
			grid.setCell(row, col, new VariableCell(0));
			// grid.printGrid();
		}
	}

	/** Calls solve for the next cell */
	public void next(int row, int col) throws Exception {
		if (col < 8)
			backtrack(row, col + 1);
		else
			backtrack(row + 1, 0);
	}
}